#pragma once


#include <time.h>
#include <assert.h>

#include <algorithm> // 算法头文件
#include <unordered_map>
#include <iostream>
#include <vector>
#include <map>

#include <thread>
#include <mutex>
#include <atomic>

using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024; // 线程池支持的申请不超过256KB，即1024字节为一个KB，总共256个KB
static const size_t NFREELIST = 208;        // 哈希桶的个数 (128 / 8 + (1024-128) / 16 ..... = 208)
static const size_t NPAGES = 129;           // PageCache的桶个数,使用直接定址法,0只负责占位,从1开始使用到128
static const size_t PAGE_SHIFT = 13;        // 一页有8K,就是2的13次方(2的10次方是1K)
static int i = 0;

//64位下,定义了32位和64位的方法,而32位下只有32位的方法
//为了让64位的能正常跑条件编译,要让64位的先被判断
#ifdef _WIN64
typedef size_t PAGE_ID; //32位下的页比较少
#elif _WIN32
typedef unsigned long long PAGE_ID; //64位下的页较多,普通的size_t存储不下
#else
typedef size_t PAGE_ID; //Linux
#endif

//跨平台的方法:条件编译
#ifdef _WIN32
#include<windows.h>
#else
#include <unistd.h>
#include <stdio.h>
void* custom_alloc(size_t size)
{
    void* curr_brk = sbrk(0);  // 获取当前program break地址[2,3](@ref)
    if (brk(curr_brk + size) == -1) // 尝试扩展堆空间
    {
        perror("brk failed");
        return NULL;
    }
    return curr_brk;  // 返回分配前的地址作为可用内存首地址[2,7](@ref)
}
#endif

// 直接去堆上按页申请空间
inline static void* SystemAlloc(size_t kpage) // 要申请多少页,一页下多少KB看系统分配或者手动修改
{
#ifdef _WIN32
    void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
    // linux下brk mmap等
    void* ptr = custom_alloc(kpage);
#endif

    //如果失败就抛异常
    if (ptr == nullptr)
        throw std::bad_alloc();

    return ptr;
}

inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
    VirtualFree(ptr, 0, MEM_RELEASE);
#else
    // sbrk unmmap等
#endif
}

static void*& NextObj(void* obj)
{
    return *(void**)obj;
}

// 返回值必须是一个引用
static void*& Nextobj(void* obj)
{
    return *((void**)obj);
}

// 管理切分好的小对象的自由链表
// ThreadCache哈希桶里的一个桶结构
class Freelist
{
public:
    void Push(void* obj)
    {
        // 头插
        //  *((void**)obj) = _freelist;
        Nextobj(obj) = _freelist;
        _freelist = obj;

        _size++;
    }



    //当给了一段小内存块时,进行头插的处理
    void PushRange(void* start, void* end, size_t n)
    {
        Nextobj(end) = _freelist;
        _freelist = start;

        _size += n;
    }

    //start是输出型参数,返回给调用函数的函数
    void PopRange(void*& start, void*& end, size_t n)
    {
        assert(n >= _size);

        start = _freelist;
        end = start;
        for (size_t i = 0; i < n - 1; i++)
        {
            end = Nextobj(end);
        }

        _freelist = Nextobj(end);
        Nextobj(end) = nullptr;
        _size -= n;

    }

    void* Pop()
    {
        assert(_freelist); // 防止出现头删为空的情况
        // 头删
        void* obj = _freelist;
        _freelist = Nextobj(_freelist);

        _size--;
        return obj;
    }
    bool Empty()
    {
        return _freelist == nullptr;
    }

    size_t Size()
    {
        return _size;
    }

    //传引用返回,后续如果maxsize成功被采用,就需要对其加加?
    size_t& Maxsize()
    {
        return _maxSize;
    }
private:
    void* _freelist = nullptr;
    size_t _maxSize = 1; //用于处理慢反馈算法,在threadcache向中心缓存取内存时用到
    size_t _size = 0;
};

// 计算对象大小的对齐映射规则
class SizeClass
{
public:
    // 整体控制在最多10%左右的内碎片浪费        哈希桶的桶数,例如1到8对应[0],121到128对应15
    // [1,128]					8byte对齐	    freelist[0,16)
    // [128+1,1024]				16byte对齐	    freelist[16,72)
    // [1024+1,8*1024]			128byte对齐	    freelist[72,128)
    // [8*1024+1,64*1024]		1024byte对齐     freelist[128,184)
    // [64*1024+1,256*1024]		8*1024byte对齐   freelist[184,208)

    static inline size_t _RoundUp(size_t size, size_t alignNum)
    {
        // 例如传进19
        //  00.....011010 --- 19+8-1 = 24
        //  11.....111000 --- ~(8-1) = ~7
        //  &了之后变为: 00.....011000 --- 24
        //  即:19对齐后变为了24
        return ((size + alignNum - 1) & ~(alignNum - 1));
    }
    // 获取对齐后的size大小,如15进来后返回的是16
    static size_t RoundUp(size_t size)
    {
        if (size <= 128)
        {
            return _RoundUp(size, 8);
        }
        else if (size <= 1024)
        {
            return _RoundUp(size, 16);
        }
        else if (size <= 8 * 1024)
        {
            return _RoundUp(size, 128);
        }
        else if (size <= 64 * 1024)
        {
            return _RoundUp(size, 1024);
        }
        else if (size <= 256 * 1024)
        {
            return _RoundUp(size, 8 * 1024);
        }
        else
        {
            // // 申请的内存大于256KB,一般是不允许的
            // assert(false);
            // return 0;
            return _RoundUp(size, 1 << PAGE_SHIFT); // 以8KB去对齐,可以自己调整
        }
    }

    // align_shift是指2的倍数方,例如3就是2的3次方
    static inline size_t _Index(size_t bytes, size_t align_shift)
    {
        //例如传入10
        //10 + 1<<3 -1 = 10+7 ==17
        //17 >> 3 == 17/8 = 2
        //因此10对应第二个哈希桶
        //由于下标的关系,还需要将得到的结果-1, 2-1 = 1号桶
        return ((bytes + (1 << align_shift - 1)) >> align_shift) - 1;
    }

    // 计算映射的哪一个自由链表桶
    static inline size_t Index(size_t bytes)
    {
        assert(bytes <= MAX_BYTES);
        // 每个对齐数,有多少个适配的桶
        // 例如8字节的对齐数,我们设置的是[1,128]都使用8字节对齐,因此就有16个桶供使用
        // 16字节的对齐数,设置的是[129,1024]区间里使用16字节对齐,因此就有56个桶供使用
        static int group_array[4] = { 16, 56, 56, 56 };
        if (bytes <= 128)
        {
            return _Index(bytes, 3);// 8bytes对齐
        }
        else if (bytes <= 1024)
        {
            //由于前面16个桶已经按照顺序排好,因此此次选桶只在该128+1到1024这个区间选，选桶看作从0号桶开始
            //所以前面的128个字节不算进选桶范围,只从129后面开始计算,即(129-128) ~ (1024-128)该区间的值被子函数收到
            //后面的数组会把桶数正确加上
            return _Index(bytes - 128, 4) - group_array[0];// 16bytes对齐
        }
        else if (bytes <= 8 * 1024)
        {
            return _Index(bytes - 1024, 7) - group_array[0] - group_array[1];// 128bytes对齐
        }
        else if (bytes <= 64 * 1024)
        {
            return _Index(bytes - 8 * 1024, 10) - group_array[0] - group_array[1] - group_array[2];// 1024bytes对齐
        }
        else if (bytes <= 256 * 1024)
        {
            return _Index(bytes - 64 * 1024, 13) - group_array[0] - group_array[1] - group_array[2] - group_array[3];// 8*1024bytes对齐
        }
        else
        {
            assert(false);
            return 0;
        }
    }

    //一次threadcache从中心缓存获取多少个
    //要的对象小就多个,要的对象多就少给
    static size_t NumMoveSize(size_t size)
    {
        assert(size > 0);
        //控制上下限
        //申请1字节时,给512个小内存块(256*1024 / 1 > 512)
        //申请256KB时,给2个小内存块(256*1024 / 256*1024 < 2)
        int num = MAX_BYTES / size;
        if (num < 2)
            num = 2;
        if (num > 512)
            num = 512;

        return num;
    }

    //计算一次向系统要几个页(1页8K)
    //单个对象 8bytes
    //...
    //单个对象 256KB
    static size_t NumMovePage(size_t size)
    {
        //即便是CentralCache向PageCache申请空间,也是要批量申请的
        size_t num = NumMoveSize(size); //要多少个size大小的数
        size_t npage = num * size;      //算出的是总的要申请的字节数

        npage >>= PAGE_SHIFT; //npage / 2^13(每次都除8K,看要多少页)
        if (npage == 0)
            npage = 1;

        return npage;
    }
private:
};

//管理多个连续页的内存跨度结构
//注意:32位和64位程序下的页号差距非常大,要用条件编译去分别定义
struct Span
{
    //页号代表的是对应PageCache的page
    PAGE_ID _pageId; //大块内存起始页的页号
    size_t _n;       //页的数量 (1页当作8KB)             

    Span* _next = nullptr;  //带头双向循环链表
    Span* _prev = nullptr;

    size_t _objSize = 0;   // 切好的小块内存的大小
    size_t _useCount = 0; // 切好小块内存,被分配给ThreadCache的计数
    void* _freeList = nullptr; //切好的小块内存的自由链表的头节点

    //例如8byte,则一个span会以8btye的大小进行切分
    size_t _objsize = 0; //每个span被切分的大小
    bool _isUse = false;  //该span是否正好被使用
};

// 带头双向循环链表
// CentralCache的哈希桶的每个桶结构
class SpanList
{
public:
    SpanList()
    {
        _head = new Span;
        _head->_next = _head;
        _head->_prev = _head;
    }

    Span* Begin()
    {
        return _head->_next;
    }
    Span* End()
    {
        //return _head->_prev;
        return _head;
    }

    bool Empty()
    {
        //真就是空
        return _head->_next == _head;
    }

    Span* PopFront()
    {
        Span* front = Begin();
        //Erase(Begin()->_next);
        Erase(Begin());
        return front; // Erase不会真的删除掉,只是让freelist指向其下一个小内存块
    }

    //头插
    void PushFront(Span* span)
    {
        Insert(Begin(), span);
    }

    void Insert(Span* pos, Span* newSpan)
    {
        assert(pos);
        assert(newSpan);

        Span* prev = pos->_prev;
        prev->_next = newSpan;
        newSpan->_prev = prev;
        newSpan->_next = pos;
        pos->_prev = newSpan;
    }

    void Erase(Span* pos)
    {
        assert(pos);
        //assert(pos != _head);
        //1.使用条件断点
        //2.使用调用堆栈
        if (pos == _head)
        {
            int x = 0;
        }

        Span* prev = pos->_prev;
        Span* next = pos->_next;

        prev->_next = next;
        next->_prev = prev;
    }
private:
    //哨兵位节点
    Span* _head;
public:
    std::mutex _mtx; //桶锁
};